package com.lhcai.nk;

/**
 * @author lhcstart
 * @create 2023-02-23 21:55
 */

import javax.sound.midi.Soundbank;
import java.util.Stack;

/**
 * 描述
 * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 * 数据范围：字符串长度 0≤n≤10000
 * 要求：空间复杂度  O(n)，时间复杂度  O(n)
 */
public class NC52 {

    public static void main(String[] args) {
        boolean valid = isValid("({})[[}]]{[]}");
        System.out.println(valid);
    }

    /**
     * @param s string字符串
     * @return bool布尔型
     */
    public static boolean isValid(String s) {
        // write code here
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];

            if (ch == '(') {
                stack.push(')');
            } else if (ch == '[') {
                stack.push(']');
            } else if (ch == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != ch) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
